import sys
import nltk
parse_table=[]
production_list=[]
production_count=0

def ckyparse(tagged_list,grammar):

    global production_count
    global parse_table
    global production_list

    production_count=0
    parse_table=[]
    production_list=[]
    
    ques_tag_pattern=""
    
    for i in tagged_list:
        ques_tag_pattern+=i[1]
        ques_tag_pattern+=" "

    ques_pattern=""
    
    for i in tagged_list:
        ques_pattern+=i[0]
        ques_pattern+=" "
    
    ques_list=ques_pattern.split()  
    ques_tag_list=ques_tag_pattern.split()
    length=len(ques_tag_list)
    
    #print ques_tag_list
    #raw_input()

    #initialize the parse_table
    for i in range(length+1):
        ml=[]
        for j in range(length+1):
            ml.append(-1)
        parse_table.append(ml)

    #first forloop of cky algorithm        
    for j in range(1,length+1):
        #table[j-1,j]<-{A|A -> words[j] E grammar
        parse_table[j-1][j]=[]
        production_list.append([{ques_tag_list[j-1]:[ques_list[j-1]]},[-1,-1],1])
        parse_table[j-1][j].append(production_count)
        production_count+=1

        add_productions(parse_table[j-1][j],production_list[production_count-1],[production_count-1,-1],grammar)
    
        #print "curr prod list= ",curr_production_list
        #raw_input()

    
        #second forloop of cky algorithm
        for i in range(j-2,-1,-1):
            parse_table[i][j]=[]
        
            #third forloop of cky algorithm
            for k in range(i+1,j):
                blist=parse_table[i][k]
                clist=parse_table[k][j]
                B=[]
                C=[]
                for tmp in blist:
                    B.append({production_list[tmp][0].keys()[0]:tmp})

                for tmp in clist:                    
                    C.append({production_list[tmp][0].keys()[0]:tmp})

                for tmp in B:
                    for tmp1 in C:
                        key=tmp.keys()[0]
                        key1=tmp1.keys()[0]
            
                        two_val=[key,key1]
                        l=get_right_productions(two_val,grammar)
                        for tmp3 in l:
                            add_this_rule={tmp3[0]:two_val}
                            production_list.append([add_this_rule,[tmp[key],tmp1[key1]],tmp3[1]])
                            parse_table[i][j].append(production_count)
                            production_count+=1
                            add_productions(parse_table[i][j],production_list[production_count-1],[production_count-1,-1],grammar)
    
        
    return [parse_table,production_list]


def add_productions(p_table_cell,production,offset,grammar):
    """ to do
    """
    to_check_production_lhs=production[0].keys()[0]
    to_check_production_rhs=production[0][to_check_production_lhs]
    global production_count
    
    for i in grammar:
        lhs=i[0].keys()[0]
        rhs=i[0][lhs]
        if rhs==[to_check_production_lhs]:
            add_this_rule={lhs:rhs}
            production_list.append([add_this_rule,offset,i[1]])
            p_table_cell.append(production_count)
            production_count+=1

            #call recursively
            add_productions(p_table_cell,production_list[production_count-1],[production_count-1,-1],grammar)
    return


def get_right_productions(rhslist,grammar):
	""" Returns 1 if A -> rhslist is present in the grammar..
	else, return 0.
	"""
	ret_list=[]
	for i in rhslist:
		if i== -1:
			return ret_list
	for i in grammar:
		lhs=i[0].keys()[0]
		rhs=i[0][lhs]
		if rhs== rhslist:
			ret_list.append([lhs,i[1]])
		
	return ret_list
    
def get_parse_tree(ptable,plist):
	"""returns the parse trees according to the parse_table, and plist
	"""
	p=ptable[0]
	p.reverse()
	any_parse=0
	last_p=p[0]
	most_probable_tree=[]
	max_prob=0.0
	if p==[]:
		print "Sorry,couldnt parse the sentence....pls check grammar"
		return []
	for i in last_p:
		if plist[i][0].keys()[0]!='ROOT':
			continue
		prob=float(plist[i][2])
		tree=['ROOT']
		app_nod1=plist[i][1][0]
		app_nod2=plist[i][1][1]
		prob*=rec_tree(tree,app_nod1,app_nod2,plist)
		if prob>max_prob:
			max_prob=prob
			most_probable_tree=tree
		
	return most_probable_tree,max_prob

def rec_tree(tree,app_nod1,app_nod2,plist):
	"""recursively parse the plist, and returns the probability of the parse
	"""
	if app_nod1==-1 and app_nod2==-1:
		return 1
	prob1=prob2=1.0
	
	if app_nod1!=-1:
		prob1=float(plist[app_nod1][2])
		rul=plist[app_nod1][0]
		tree.append([rul.keys()[0]])
		new_app_nod2=plist[app_nod1][1][1]
		new_app_nod1=plist[app_nod1][1][0]
		if new_app_nod1==-1 and new_app_nod2==-1:
			tree[-1].append(rul[rul.keys()[0]])
		else:
			prob1*=rec_tree(tree[-1],new_app_nod1,new_app_nod2,plist)
	
	if app_nod2!=-1:
		prob2=float(plist[app_nod2][2])
		rul=plist[app_nod2][0]
		tree.append([rul.keys()[0]])
		new_app_nod1=plist[app_nod2][1][0]
		new_app_nod2=plist[app_nod2][1][1]
		if new_app_nod1==-1 and new_app_nod2==-1:
			tree[-1].append(rul[rul.keys()[0]])
		else:
			prob2*=rec_tree(tree[-1],new_app_nod1,new_app_nod2,plist)

	return prob1*prob2

def gen_grammar(filename):
    ip=open('E:\project\\aqas\grammar\grammar.cfg',"r")
    flag=0
    grammar=[]
    while True:
        lin=ip.readline()
        if lin=='':
            break
        words=lin.split()
        if len(words)==4:
            g_dict={words[0]:[words[2]]}
            grammar.append([g_dict,words[3]])
        if len(words)==5:
            g_dict={words[0]:[words[2],words[3]]}
            grammar.append([g_dict,words[4]])
    return grammar
    


def test_parse(t):
    g=gen_grammar('')
    toks=nltk.word_tokenize(t)
    tags=nltk.pos_tag(toks)
    ptable,plist=ckyparse(tags,g)
    #tree=get_parse_trees(ptable,plist)
    #print tree
    count=0
    #for i in plist:
    #   print count,i,"\n"
    #  count+=1
        
    tree,prob=get_parse_tree(ptable,plist)
    return tree
